from typing import *


class Solution:

    # 执行用时：156 ms, 在所有 Python3 提交中击败了50.43%的用户
    # 内存消耗：19.5 MB, 在所有 Python3 提交中击败了7.69%的用户
    # 通过测试用例：89 / 89

    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnts = DefaultDict(int)
        for row in matrix:
            f = row[0]
            for i in range(len(row)):
                row[i] ^= f
            cnts[tuple(row)] += 1
        return max(cnts.values())


class Solution:

    # 执行用时：152 ms, 在所有 Python3 提交中击败了52.14%的用户
    # 内存消耗：19.2 MB, 在所有 Python3 提交中击败了16.24%的用户
    # 通过测试用例：89 / 89

    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnts = Counter()
        for row in matrix:
            f = row[0]
            for i in range(len(row)):
                row[i] ^= f
            cnts[tuple(row)] += 1
        return max(cnts.values())


class Solution:

    # 执行用时：104 ms, 在所有 Python3 提交中击败了82.05%的用户
    # 内存消耗：19.4 MB, 在所有 Python3 提交中击败了14.53%的用户
    # 通过测试用例：89 / 89

    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnts = Counter()
        for row in matrix:
            if row[0] == 1:
                for i in range(len(row)):
                    row[i] ^= 1
            cnts[tuple(row)] += 1
        return max(cnts.values())


class Solution:

    # 执行用时：176 ms, 在所有 Python3 提交中击败了40.17%的用户
    # 内存消耗：18.9 MB, 在所有 Python3 提交中击败了25.64%的用户
    # 通过测试用例：89 / 89

    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnts = Counter()
        for row in matrix:
            if row[0] == 1:
                for i in range(len(row)):
                    row[i] ^= 1
            cnts["".join(map(str, row))] += 1
        return max(cnts.values())


test = Solution()
print(test.maxEqualRowsAfterFlips(matrix=[[0, 1], [1, 1]]))
print(test.maxEqualRowsAfterFlips(matrix=[[0, 1], [1, 0]]))
print(test.maxEqualRowsAfterFlips(matrix=[[0, 0, 0], [0, 0, 1], [1, 1, 0]]))
